Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

 

Solution

首先使用[LeetCode 141. Linked List Cycle]中的方法判断是否存在环。

若中节点的个数为N个，环外的节点为M个，总节点数就是N+M个。一个指针处于环的入口处的条件是该指针一共走了M+kN步（k=0,1,2,3,…）。因此只要定义两个指针，最开始都指向链表开头。先将使其中一个指针向前移动N步（此时对两个指针来说都需要再走M步就能到达环的开始结点），然后一起向前移动直到地址相等，相等处的节点即是环的开始节点。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    ListNode *detectCycle(ListNode *head)
    {
        if(head == NULL) return head;
        ListNode *fast = head->next, *slow = head;
        while(true)
        {
            if(fast == NULL || slow == NULL) return NULL;
            if(fast == slow)
            {
                break;
            }
            if(fast->next != NULL)
            {
                fast = fast->next;
            }
            else
            {
                return NULL;
            }
            fast = fast->next;
            slow = slow->next;
        }
        ListNode *save = fast;
        fast = fast->next;
        int stepInLoop = 1;
        while(fast != save)
        {
            stepInLoop++;
            fast = fast->next;
        }
        fast = head, slow = head;
        while(stepInLoop--) fast = fast->next;
        while(true)
        {
            if(fast == slow) break;
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};